|
課程名稱 |
演算法
Algorithms |
|
開課學期 |
109-2 |
|
授課對象 |
電機資訊學院 電機工程學系 |
|
授課教師 |
江蕙如 |
|
課號 |
EE4033 |
|
課程識別碼 |
901 39000 |
|
班次 |
|
|
學分 |
3.0 |
|
全/半年 |
半年 |
|
必/選修 |
必修 |
|
上課時間 |
星期四2,3,4(9:10~12:10) |
|
上課地點 |
博理112 |
|
備註 |
總人數上限：80人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1092EE4033 |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
The study of algorithms is at the heart of computer science. This course focuses on fundamental results in this area, including the unifying principles and underlying concepts of algorithm design and analysis.
We expect everyone to be comfortable reading, even writing, proofs. Several programming assignments will be given to embody the ideas. Moreover, we hope that everyone can learn general problem-solving techniques. |
|
課程目標 |
1. Study unifying principles and concepts of algorithm design and analysis
2. Polish your critical thinking and problem-solving technique |
|
課程要求 |
Prerequisite: two out of the following four courses
1. Data structures
2. Discrete mathematics
3. Computer programming in C
4. Computer programming in C++
*** C/C++ programming skill is a must *** |
|
預期每週課後學習時數 |
|
|
Office Hours |
每週三 12:30~13:30 備註： by appointment |
|
指定閱讀 |
Text book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to
Algorithms, 3rd Ed., McGraw Hill/MIT Press, 2009 (Bible! MIT)
|
|
參考書目 |
Recommended books on algorithms:
1. J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006
(Cornell)
2. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, McGraw-
Hill, 2007 (UC Berkeley)
Recommended books on graph theory:
1. Douglas B. West, Introduction to Graph Theory, 2nd Edition, Pearson, 2000.
2. 演算法觀點的圖論 (Graph Theory, with an Algorithmic Perspective)作者：張鎮華 |
|
評量方式
(僅供參考) |
|
No. |
項目 |
百分比 |
說明 |
|
1. |
Five homework assignments |
18% |
|
2. |
DIY |
2% |
|
3. |
Five in-class quizzes |
5% |
|
4. |
Three programming assignments |
25% |
|
5. |
Midterm |
20% |
|
6. |
Final |
30% |
|
7. |
Bonus |
0% |
|
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
|
Foundations: Ch1, Ch2, Ch3 |
|
第2週 |
|
Foundations (Divide-and-Conquer): Ch2.3, Ch4 |
|
第3週 |
|
Sorting: Ch6 , Ch7 |
|
第4週 |
|
Sorting: Ch8, Ch9 |
|
第5週 |
|
Trees: Ch12 |
|
第6週 |
|
Trees: Ch13 |
|
第7週 |
|
Advanced Design (Dynamic Programming): Ch15 |
|
第8週 |
|
Advanced Design (Dynamic Programming): Ch15 |
|
第9週 |
|
Midterm Exam 9:20-12:10 |
|
第10週 |
|
Advanced Design (Greedy Algorithms): Ch16 |
|
第11週 |
|
Graphs BFS/DFS: Ch22 |
|
第12週 |
|
Graphs MST: Ch23
Disjoint Set: Ch21 |
|
第13週 |
|
Graphs SSSP: Ch24 |
|
第14週 |
|
Graphs APSP: Ch25 |
|
第15週 |
|
Graphs Flow: Ch26 |
|
第16週 |
|
NP-completeness: Ch34,35.1~35.2 |
|
第17週 |
|
Advanced topics
Amortized Analysis: Ch17 |
|
第18週 |
|
Final Exam 9:20-12:10 |
|